package 回溯;

/**
 * 我假设正则表达式中只包含“*”和“?”这两种通配符，并且对这两个通配符的语义稍微做些改变，
 * 其中，“*”匹配任意多个（大于等于 0 个）任意字符，“?”匹配零个或者一个任意字符。
 */
public class 正则表达式 {

    public static class Pattern{

        private boolean matched = false;

        private char[] pattern;

        private int plen;


        public Pattern(String pattern) {
            this.pattern = pattern.toCharArray();

            plen = pattern.length();
        }

        public boolean match(String text){
            matched = false;
            rmatch(0,0 ,text.toCharArray() ,text.length() );
            return matched;
        }

        private void rmatch(int curplen,int curtlen,char[] text,int tlen){
            if (matched){
                return;
            }
            if (curplen == plen){
                if (curtlen == tlen){
                    matched = true;
                }
                return;
            }
            if (pattern[curplen] == '*'){
                for (int i = curtlen; i <= tlen; i++) {
                    rmatch(curplen+1,i ,text ,tlen );
                }
            }else if (pattern[curplen] == '?'){
                rmatch(curplen+1,curtlen ,text ,tlen );
                rmatch(curplen+1,curtlen+1 ,text ,tlen );
            }else {
                if (curtlen < tlen && pattern[curplen] == text[curtlen]){
                    rmatch(curplen+1,curtlen+1 ,text ,tlen );
                }else {
                    return;
                }
            }
        }
    }

    public static void main(String[] args) {
        Pattern pattern = new Pattern("a*a?b");
        boolean match = pattern.match("a2314easb");
        System.out.println(match);
    }



}
